from collections import defaultdict

N = int(1e5)
'''
Tarjan算法一遍不一定能搜完所有的点。所以我们要对一趟跑下来还没有被访问到的点继续跑Tarjan 
判断依据就是看dfn[i]是否为0。
'''

adj = defaultdict(list)

dfn = [0] * N
low = [0] * N
dfncnt = 0
s = [0] * N  # 模拟栈操作
in_stack = [0] * N
tp = 0
scc = [0] * N
sc = 0  # 结点 i 所在 SCC 的编号
sz = [0] * N  # 强连通 i 的大小


def tarjan(u):
    global dfn, dfncnt, tp, sc
    low[u] = dfn[u] = dfncnt
    s[tp] = u
    in_stack[u] = 1
    dfncnt = dfncnt + 1
    tp = tp + 1
    for v in adj[u]:
        if not dfn[v]:
            tarjan(v)
            low[u] = min(low[u], low[v])
        elif in_stack[v]:
            low[u] = min(low[u], dfn[v])
    if dfn[u] == low[u]:
        sc = sc + 1
        while s[tp] != u:
            scc[s[tp]] = sc
            sz[sc] = sz[sc] + 1
            in_stack[s[tp]] = 0
            tp = tp - 1
        scc[s[tp]] = sc
        sz[sc] = sz[sc] + 1
        in_stack[s[tp]] = 0
        tp = tp - 1
